package main

import (
	"fmt"
)

type MaxPQ struct {
	//save element
	pq []int
	//the number of pq element(no包括前置0)
	size int
}

func InitMaxPQ(cap int) *MaxPQ {
	return &MaxPQ{
		pq:   make([]int, 1, cap+1),
		size: 0,
	}
}

func (p *MaxPQ) parent(x int) int {
	return x / 2
}

func (p *MaxPQ) left(x int) int {
	return x * 2
}

func (p *MaxPQ) right(x int) int {
	return x*2 + 1
}

//MaxVal return MAX value of MaxPQ
func (p *MaxPQ) MaxVal() int {
	//fmt.Println(len(p.pq), cap(p.pq))
	if p.size < 1 {
		panic("no elements in MaxPQ")
	}
	return p.pq[1]
}

//Insert to insert an element
func (p *MaxPQ) Insert(e int) {
	p.pq = append(p.pq, e)
	p.size += 1

	p.swim(p.size)
	//fmt.Println(p)
}

//DelMax 删除并返回最大值
func (p *MaxPQ) DelMax() (max int) {
	max = p.pq[1]
	p.swap(1, p.size)
	p.pq = append(p.pq[:len(p.pq)-1], p.pq[len(p.pq):]...)
	p.size -= 1

	p.sink(1)
	return
}

//swim 上浮第x个元素
func (p *MaxPQ) swim(x int) {
	node := x
	for {
		//如果是根节点 或者 节点值小于父节点值
		if node == 1 || p.less(node, p.parent(node)) {
			//停止上浮
			break
		}
		//开始交换
		p.swap(node, p.parent(node))
		node = p.parent(node)
	}
}

//sink 下沉第x个元素
func (p *MaxPQ) sink(x int) {
	node := x
	bigger := p.left(node)
	for {
		//沉到底了就不再沉了
		if bigger > p.size {
			break
		}
		//如果右节点存在并且比左结点大 那么就和右节点交换
		if p.right(node) <= p.size && p.less(bigger, p.right(node)) {
			bigger = p.right(node)
		}
		//如果子节点中最大的比自己还小 就不用下沉了
		if p.less(bigger, node) {
			break
		}
		//否则 继续下沉
		p.swap(bigger, node)
		node = bigger
		bigger = p.left(node)
	}
}

//swap 交换两个元素
func (p *MaxPQ) swap(i, j int) {
	temp := p.pq[i]
	p.pq[i] = p.pq[j]
	p.pq[j] = temp
}

//less 比较两个元素大小
func (p *MaxPQ) less(i, j int) bool {
	return p.pq[i] < p.pq[j]
}

func main() {
	fmt.Println("test")
	t := InitMaxPQ(5)
	fmt.Println(t)

	t.Insert(1)
	fmt.Println("1 -> ", t)
	t.Insert(6)
	fmt.Println("6 -> ", t)
	t.Insert(5)
	fmt.Println("5 -> ", t)

	fmt.Println(t.MaxVal())

	fmt.Println(t.DelMax())
	fmt.Println("delet max -> ", t)

}
